package leetcode_top;
import java.util.*;
import org.junit.*;
public class Ex134 {
    class Solution1 {
        class Node {
            int idx;
            double val;

            public Node(int idx, double val) {
                this.idx = idx;
                this.val = val;
            }

        }
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int len = gas.length;
            double[] vals = new double[len];
            int min = 0;
            for (int i = 0; i < len; i++) {
                vals[i] = gas[i] / (double)cost[i];
                if (vals[i] < vals[min]) {
                    min = i;
                }
            }
            Queue<Node> queue = new PriorityQueue<>((n1, n2) -> n2.val - n1.val > 0 ? 1 : 0);
            for (int i = 0; i < len; i++) {
                if (i != min) {
                    queue.offer(new Node(i, vals[i]));
                }
            }

            int cur = gas[min];
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                cur -= (cost[node.idx] - gas[node.idx]);
                if (cur < 0) return -1;
            }
            return min;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(s.canCompleteCircuit(nums, cost));
    }

    class Solution2 { //只能去往隔壁的加油站
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int len = gas.length;
            for (int i = 0; i < len; i++) {
                if (testRight(gas, cost, i, gas[i], i)) {
                    return i;
                }
            }
            return -1;
        }

        public boolean testRight(int[] gas, int[] cost, int start, int cur, int idx) {
            int len = gas.length;
            int last = -1;
            while (last != start) {
                last = idx == len - 1 ? 0 : idx + 1;
                cur = cur - cost[idx];
                if (cur < 0) return false;
                cur += gas[last];
                idx = last;
            }
            return true;
        } 
    }

    /* 
        很简单的逻辑：
        若是i只能到达j，那么从i~j的多有点都不能绕一圈！
        
        反证法：
        若是 k ∈ (i, j)， k可以绕一圈
        因为i可以到达j，因此i到达k时 cur >= 0
        而k可以绕一圈，那么k出发时为0即<=cur
        而既然cur>=0的i都做不到，k肯定也做不到

    */    class Solution { //只能去往隔壁的加油站
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int len = gas.length, cur;
            for (int i = 0; i < len; i++) {
                cur = gas[i];
                int j = i;
                while (cur >= cost[j]) {
                    cur = cur - cost[j] + gas[(j = (j + 1) % len)];
                    if (i == j) return i;
                }
                if (cur < cost[j] && j != i) return -1;
                i = j;
            }
            return -1;
        }

    
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int j = i;
            int remain = gas[i];
            while (remain - cost[j] >= 0) {
                //减去花费的加上新的点的补给
                remain = remain - cost[j] + gas[(j + 1) % n];
                j = (j + 1) % n;
                //j 回到了 i
                if (j == i) {
                    return i;
                }
            }
            //最远距离绕到了之前，所以 i 后边的都不可能绕一圈了
            if (j < i) {
                return -1;
            }
            //i 直接跳到 j，外层 for 循环执行 i++，相当于从 j + 1 开始考虑
            i = j;
    
        }
        return -1;
    }



}
